#include "bigint.h"
#include <algorithm>
#include <fstream>


BigInt::BigInt ( size_t size )
	:size_( size ), data_( new int[size] ), isNegative_( false )
{
	for ( size_t i = 0; i != size_; ++i ){
		data_[i]  = 0;
	}
}

BigInt::BigInt ( int * src, size_t size, bool negative ) 
	:size_( size ), data_( new int[size] ), isNegative_( negative )
{
	for ( size_t i = 0; i != size_; ++i ){
		data_[i] = src[size_ - i - 1];
	}          		
}

BigInt::BigInt ( BigInt const & bi )
	:size_( bi.size_ ), data_( new int[size_] ), isNegative_( bi.isNegative_ )
{
	for ( size_t i = 0; i != size_; ++i ){
		data_[i] = bi.data_[i];
	}
}
		
BigInt::BigInt ( std::string const & str ){
	size_t i = 0;
		
	if ( str[0] == '-' ){
		isNegative_ = true;
		++i;
	}else{
		isNegative_ = false;
	}

	while ( str[i] == '0' ){
		++i;
	}

	size_ = str.length() - i;
	
	if ( size_ == 0 ){
		size_ = 1;
		isNegative_ = false;
		data_ = new int[size_];
		data_[0] = 0;
	}else{
		data_ = new int[size_];		    	
		for ( size_t j = i; j != str.length(); ++j ){
			data_[j - i] = str[str.length() - j + i - 1] - '0';
		}
	}
		
}

BigInt::~BigInt (){
	size_ = 0;
	delete [] data_;
}

size_t BigInt::size () const{
	return size_;
}

int * BigInt::data () const {
	return data_;
}

bool BigInt::isNegative () const {
	return isNegative_;
}

int BigInt::data (size_t pos) const{
	return data_[pos];
}

	
std::ofstream & operator<< ( std::ofstream & out, BigInt & n) {
	if ( n.isNegative() ){
		out << "-";
	} 
	size_t i = 0;
	while (n.data()[n.size() - i - 1] == 0 && i < n.size() - 1){
		++i;
	}
	for ( ; i != n.size(); ++i ){
		out << n.data()[n.size() - i - 1] ;
	}
	return out;
}

void BigInt::addAbs ( BigInt const & b1, BigInt const & b2 ){	
	size_t size_max = std::max( b1.size_, b2.size_ );
	size_t size_min = std::min( b1.size_, b2.size_ );

	int * temp = new int[size_max + 1];

	for ( size_t i = 0; i != size_max + 1; ++i ){
		temp[i] = 0;
	}
	
	BigInt const * big = &b1;
	BigInt const * small = &b2;

	if (b1.size_ == size_min){
		big = &b2;
		small = &b1;
	}

	for (size_t i = 0; i != size_max; ++i){
		if (i < size_min){           
			if ( temp[i] + (*big).data_[i] + (*small).data_[i] >= 10 ){                       
				temp[i] += (*big).data_[i] + (*small).data_[i] - 10;
				temp[i+1] = 1;          
			}else{
				temp[i] += (*big).data_[i] + (*small).data_[i];
			}       
		}else{
			if ( temp[i] + (*big).data_[i] >= 10 ){                  
				temp[i] += (*big).data_[i] - 10;
				temp[i+1] = 1;          
			}else{
				temp[i] += (*big).data_[i];
			}
		}
    }
	update(temp, size_max, b1.isNegative_);
	delete [] temp;	
}



int BigInt::isBigger ( BigInt const & bi ) const{
	if ( size_ > bi.size_ ){
		return 1;
	}
	
	if ( size_ < bi.size_ ){
		return 0;
	}

	size_t i = size_ - 1;
	
	while ( i != -1 && data_[i] == bi.data_[i] ){
		--i;
	}
	
	if ( i == -1 ){
		return -1;
	}
	if ( data_[i] > bi.data_[i] ){
		return 1;
	}else{
		return 0;
	}		
}



void BigInt::subAbs ( BigInt const & b1, BigInt const & b2 ){
	if ( b1.isBigger(b2) == -1 ){
		isNegative_ = false;
		delete [] data_;
		size_ = 1;
		data_ = new int[size_];
		data_[0] = 0;
		return;
	}
	
	size_t size_max = std::max(b1.size_, b2.size_);
	size_t size_min = std::min(b1.size_, b2.size_);

	int * temp = new int[size_max];              

	for ( size_t i = 0; i != size_max; ++i ){
		temp[i] = 0;
	}
	BigInt const * big = &b2;
	BigInt const * small = &b1;
	if (b1.isBigger(b2)){
		big = &b1;
		small = &b2;
	}

	for ( size_t i = 0; i != size_min; ++i ){
		if ( temp[i] + (*big).data_[i] - (*small).data_[i] < 0 ){
			temp[i] += (*big).data_[i] - (*small).data_[i] + 10;
			temp[i+1] -= 1;
			
		}else{
			temp[i] += (*big).data_[i] - (*small).data_[i];
		}                          			
	}	
	for ( size_t i = size_min; i != size_max; ++i ){
		if ( (*big).data_[i] + temp[i] < 0 ){
			temp[i] += (*big).data_[i] + 10;
			temp[i+1] = -1;
		}else{
			temp[i] += (*big).data_[i];
		}   
	}
	
	isNegative_ = (*big).isNegative_;

	while ( temp[size_max - 1] == 0 ){
		--size_max;
	} 

	update(temp, size_max, isNegative_);
	
	delete [] temp;
}

void BigInt::update ( int * src, size_t size, bool negative){
	delete [] data_;	
	size_ = size;
	data_ = new int[size_];	
	for ( size_t i = 0; i != size; ++i ){
		data_[i] = src[i];
	}     	
	isNegative_ = negative;
}

BigInt & BigInt::operator*= ( int i ){

	size_t size = size_ + 1;
	int * temp = new int[size];

	for ( size_t j = 0; j != size; ++j ){
		temp[j] = 0;
	}

	for ( size_t j = 0; j != size_; ++j ){
		if ( temp[j] + i * data_[j] >= 10 ){
			temp[j + 1] += (temp[j] + i * data_[j]) / 10;
			temp[j] = (temp[j] + i * data_[j] ) % 10;
		}else{
          	temp[j] += i * data_[j];
		}
	}

	while ( temp[size - 1] == 0 && size > 1 ){
		--size;
	}

	delete [] data_;
	data_ = temp;
	size_ = size;
	return *this;
}

BigInt & operator* ( BigInt const & b1, int i ){
	BigInt * b = new BigInt(b1);
	*b *= i;
	return *b;
}

BigInt & BigInt::operator*= ( BigInt const & b2 ){
	BigInt * b = new BigInt(*this);
	*this -= *this;
	for ( size_t i = 0; i != b2.size_; ++i ){
	    BigInt & a(*b * b2.data_[i]);
	    a.shift(i);
		*this += a;
	}

	isNegative_ = (*b).isNegative_ ^ b2.isNegative_;
	if (size_ == 1 && data_[0] == 0){	
		isNegative_ = false;       
	}
	return *this;
}

BigInt & BigInt::shift ( size_t i ){
	int * temp = new int[i + size_];
	for (size_t j = 0; j != i; ++j){
		temp[j] = 0;
	}
	for (size_t j = i; j != i + size_; ++j){
		temp[j] = data_[j-i];
	}
	delete [] data_;
	size_ = i + size_;
	data_ = temp;
	return *this;
}


BigInt & operator* ( BigInt const & b1, BigInt const & b2 ){
	BigInt * b = new BigInt(b1);
	*b *= b2;
	return *b;
}

void BigInt::swap( BigInt & bi ){
	std::swap(data_, bi.data_);
	std::swap(size_, bi.size_);
	std::swap(isNegative_, bi.isNegative_);
}


BigInt & BigInt::operator= ( BigInt const & bi ){
	if ( this != &bi ){
	    BigInt(bi).swap(*this);
		return *this;
	}
}

bool operator== (BigInt const & b1, BigInt const & b2) {
	if (b1.size() == b2.size() && b1.isNegative() == b2.isNegative()){
		size_t i = b1.size() - 1;
		while ( i != -1 && b1.data(i) == b2.data(i) ){
			--i;
		} 
		if (i == -1){
			return true;
		}
	}
	return false;
}

bool operator!= (BigInt const & b1, BigInt const & b2) {
	return !(b1 == b2);
}

bool operator< (BigInt const & b1, BigInt const & b2) {
	if (b1.isNegative() && !b2.isNegative()) return true;
	if (!b1.isNegative() && b2.isNegative()) return false;

	if (b1 == b2) return false;
	
	if (b1.size() < b2.size()) {
	    return !b1.isNegative();                        
	}else{             
		return b1.isNegative();
	}
		
	size_t i = b1.size() - 1;
		
	while ( i != -1 && b1.data()[i] == b2.data()[i] ){
		--i;
	} 
	if (b1.data()[i] < b2.data()[i]){
		return !b1.isNegative();                          
	}else{
		return b1.isNegative();
	}

}

bool operator> (BigInt const & b1, BigInt const & b2) {
	return (b2 < b1);
}

bool operator>= (BigInt const & b1, BigInt const & b2) {
	return !(b1 < b2);
}

bool operator<= (BigInt const & b1, BigInt const & b2) {
	return !(b1 > b2);
}

void BigInt::setNegative(bool negative){
	isNegative_ = negative;
}

BigInt & operator- (BigInt const & bi){
	BigInt * b = new BigInt(bi);
	(*b).setNegative(!bi.isNegative());
	return *b;
}                 

BigInt & BigInt::operator-= ( BigInt const & b2 ){
    return *this += -b2;
}

BigInt & operator- ( BigInt const & b1, BigInt const & b2){
	BigInt * b = new BigInt(b1);
	*b -= b2;
	return *b;
}

BigInt & BigInt::operator+= (BigInt const & b2){	
	if (isNegative() == b2.isNegative()){
		addAbs(*this, b2);
	}else{
		if (isNegative()){
			subAbs(b2, *this);
		}else{
			subAbs(*this, b2);
		}
	}
	return *this;
}

BigInt & operator+ ( BigInt const & b1, BigInt const & b2 ){
	BigInt * b = new BigInt(b1);
	*b += b2;    
	return *b;	
}
